/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ringstarproject;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class TSP_data {
    
        private int iterationMax = 1000;

	private String path="";

	private ArrayList<Double> x = new ArrayList<Double>();
	private ArrayList<Double> y = new ArrayList<Double>();
	private List<Integer> intervalleAlpha = Arrays.asList(3,5,7,9);
	private Double distance[][];		// lij
	private Double coutCycle[][];  		// cij
	private Double coutAffectation[][]; // dij
        private ArrayList<Integer> sommetsCycle = new ArrayList<Integer>();
        private ArrayList<Integer> sommetsRestants = new ArrayList<Integer>();
        private Double lambda = 0.5;

       private ArrayList<Arete> inseres = new ArrayList<Arete>();
       private ArrayList<Arete> retires = new ArrayList<Arete>();

    public Double[][] getCoutAffectation() {
        return coutAffectation;
    }

    public Double[][] getCoutCycle() {
        return coutCycle;
    }

    public Double[][] getDistance() {
        return distance;
    }

    public String getPath() {
        return path;
    }

    public ArrayList<Integer> getSommetsCycle() {
        return sommetsCycle;
    }

    public ArrayList<Integer> getSommetsRestants() {
        return sommetsRestants;
    }

    public ArrayList<Double> getX() {
        return x;
    }

    public ArrayList<Double> getY() {
        return y;
    }

	private int dim;
	private int alpha;
        private long timeHeuristique;
        private double coutTotal;
        private boolean useGraphics;

	public TSP_data(boolean graphical)
	{
                useGraphics = graphical;
                initFichier();

		readFile();            
                initMatrices();
                remplirMatrices();
                printCoutCycle();
                printCoutAffectation();

                long timeDeb = System.currentTimeMillis();
                calculHeuristique();
                timeHeuristique = System.currentTimeMillis() - timeDeb;
                printCycle();

                if(useGraphics)
                {
                  TSPtoDGS graph = new TSPtoDGS();
                  graph.createDGSFile(this);
                }
                timeDeb = System.currentTimeMillis();
		metaHeuristique();
                timeHeuristique = System.currentTimeMillis() - timeDeb;
                printCycle();
                if(useGraphics)
                {
                  TSPtoDGS graph = new TSPtoDGS();
                  graph.createDGSFile(this);
                }

		System.out.println("\n\nTerminé");
	}

        public void initFichier( )
        {
            int choix = 0;
            Scanner sc = new Scanner(System.in);
            do{
               System.out.print("Choisir le fichier : \n1. Eil51.esp\n2. Eil101.tsp\n3. test.esp\n  --> Choix : ");
               choix = sc.nextInt();
            }while(choix < 1 || choix > 3);

            path = "instances/";
            switch(choix)
            {
                case 1:
                    path += "eil51.tsp";
                    break;

                case 2:
                    path += "eil101.tsp";
                    break;

                case 3:
                    path += "test.tsp";
                    break;
            }


            do{
               System.out.print("\nChoisir Alpha parmi 3,5,7,9 : " );
               alpha = sc.nextInt();
            }while(!intervalleAlpha.contains(alpha));
        }

	public void readFile()
	{
			//lecture du fichier texte
			try{
				InputStream ips=new FileInputStream(path);
				InputStreamReader ipsr=new InputStreamReader(ips);
				BufferedReader br=new BufferedReader(ipsr);
				String ligne;
				while ((ligne=br.readLine())!=null){
					// récupère la dimension
					if(ligne.startsWith("D")){
						String[] tmp=ligne.split(":");
						setNbSommets(Integer.decode(tmp[1].trim()));
					}

					// début des données à récupèrer
					if(ligne.startsWith("NODE")){
						while (!(ligne=br.readLine()).equals("EOF")){
							String[] tmp=ligne.split(" ");
							x.add(Double.parseDouble(tmp[1].trim()));
							y.add(Double.parseDouble(tmp[2].trim()));
                                                     
						}
					}

				}
				br.close();
                        

			}
			catch (FileNotFoundException ex1){
				System.out.println("--> Fichier introuvable");
			}
			catch (NullPointerException ex2){
				System.out.println("--> Null Pointer");
			}
			catch (Exception ex3){
				System.out.println("--> Erreur dans l'analyse des donnée");
			}

	}

	/* initialise les matrices à 0 */
	public void initMatrices(){
		distance = new Double[dim][dim];
		coutAffectation = new Double[dim][dim];
		coutCycle = new Double[dim][dim];

		for(int i=0; i<dim; i++){
			for(int j=0; j<dim; j++){
				distance[i][j]=0.0;
				coutAffectation[i][j]=0.0;
				coutCycle[i][j]=0.0;
			}
		}
	}

	public int getNbSommets()
	{
		return this.dim;
	}
	public void setNbSommets(int nb)
	{
		this.dim = nb;
	}

    public void printCoutAffectation() {
        System.out.println("\n\n-------------------------------------");
		System.out.println("Coûts d'affectation");
		System.out.println("-------------------------------------\n");
		for(int i=0; i<dim; i++){
			System.out.print("[");
			for(int j=0; j<dim; j++){
				System.out.print(coutAffectation[i][j]+"  " );
			}
			System.out.println("]");
		}
    }

    public void printCoutCycle() {
       		System.out.println("-------------------------------------");
		System.out.println("Coûts du cycle");
		System.out.println("-------------------------------------\n");
		for(int i=0; i<dim; i++){
			System.out.print("[");
			//for(int j=i+1; j<dim; j++){
                        for(int j=0; j<dim; j++){
				System.out.print(coutCycle[i][j] +"  " );
			}
			System.out.println("]");
		}
    }

    public void remplirMatrices() {

            /* Rempli les affectations selon les valeurs du fichiers, et du calculs des cij, dij de classe I */
            for(int i=0; i<dim; i++){
                sommetsRestants.add(i+1);
                for(int j=i+1; j<dim; j++){
                            distance[i][j]= distance[j][i] = Math.sqrt((x.get(i)-x.get(j))*(x.get(i)-x.get(j)) + ((y.get(i)-y.get(j))*(y.get(i)-y.get(j))) + 0.5);
                            coutCycle[i][j] = coutCycle[j][i] = Math.ceil(alpha * distance[i][j]);
                            coutAffectation[i][j] = coutAffectation[j][i] = Math.ceil( (10-alpha)* distance[i][j]);
                    }
            }
    }

    public void calculHeuristique() {


        //pour stocker le retour de chercheCoutCycleMin
        // contient : coutMin ; x ; y
        Double tab[];

        creerCycleMin();
        coutTotal = calculCoutTotal(sommetsCycle, true);

       double L = 0;
       double meilleurInc = 0;
       double meilleurDec = 0;
       int meilleurSommet = 0;
       int meilleurSommet1 = 0;
       int sommetAInserer;
       do
       {
           L= 0;
           meilleurSommet = 0;
           for(int i=0 ; i<sommetsRestants.size(); i++){
               
              for(int j = 0 ; j< sommetsCycle.size(); j++)
                {
                    int sommet1,sommet2;
                    double inc,dec;

                    sommetAInserer = sommetsRestants.get(i);
                    sommet1 = sommetsCycle.get(j);
                    if( j == sommetsCycle.size()-1 )
                        sommet2 = sommetsCycle.get(0);
                    else
                        sommet2 = sommetsCycle.get(j+1);

                    inc = calculeInc(sommetAInserer, sommet1, sommet2);
                    dec = calculeDec(sommetAInserer);
                    double Li = lambda*inc + (1-lambda)*(-dec);

                    if(Li < L)
                    {
                        L = Li;
                        meilleurSommet1 = sommet1;
                        meilleurSommet = sommetAInserer;
                        meilleurInc = inc ;
                        meilleurDec = dec;
                    }
                }
            }
           //ajoute sommet trouvé dans le cycle
           if( L < 0)
           {

              // System.out.println("L : " + (meilleurInc - meilleurDec));
               ajouterSommet(meilleurSommet,meilleurSommet1);
               coutTotal += (meilleurInc - meilleurDec);

           }

       }while(L < 0);


    }

    private Double calculeInc(int vi,int sommet1, int sommet2)
    {
        double inc = coutCycle[vi-1][(int)sommet1-1] + coutCycle[vi-1][(int)sommet2-1] - coutCycle[(int)sommet1-1][(int)sommet2-1];
        
        return inc;

    }
    
    public int plusProcheSommetCycle(int vi)
    {
        double cout = 0;
        int sommet = 0;
        for(int i =0 ; i < sommetsCycle.size() ; i++)
        {
            if(coutCycle[vi-1][sommetsCycle.get(i)-1] < cout || cout == 0)
            {
               cout = coutCycle[vi-1][sommetsCycle.get(i)-1];
               sommet = sommetsCycle.get(i);
            }
        }

        return sommet;
    }

    private double calculeDec(int vi)
    {
        double dec = 0;
        int plusProcheSommet = plusProcheSommetCycle(vi);

        dec = coutAffectation[vi-1][(int)plusProcheSommet-1];

        for(int i = 0; i < sommetsRestants.size() ; i++)
        {
            if( sommetsRestants.get(i) != vi)
            {
                double ancienCout = coutAffectation[sommetsRestants.get(i)-1][plusProcheSommetCycle(sommetsRestants.get(i))-1];
                double nouveauCout = coutAffectation[sommetsRestants.get(i)-1][vi-1];

                if( nouveauCout < ancienCout)
                    dec += ancienCout - nouveauCout;
            }
        }

        return dec;
    }

    // ajoute notre sommet dans le cycle en le supprimant des sommets restants
    public void ajouterSommet(int sommet, int avant)
    {
        int indiceDebut = 0;
        for(int i = 0; i < sommetsCycle.size() ; i ++)
            if( sommetsCycle.get(i) == avant )
                 indiceDebut = i+1;


            for(int i = 0 ; i < sommetsRestants.size() ; i++)
                if( sommetsRestants.get(i) == sommet)
                        sommetsRestants.remove(i);
            // décale tous les sommets pour insérer le nouveau
            if( avant == -1 || indiceDebut == sommetsCycle.size())
            {
                sommetsCycle.add(sommet);//sommetsCycle.get(sommetsCycle.size()-1));
               // for(int i = sommetsCycle.size(); i > indiceDebut ; i--)
                 //    sommetsCycle.set(i-1, sommetsCycle.get(i-2));

                //insere le nouveau
                 //sommetsCycle.set(indiceDebut,sommet);
            }
            else
                sommetsCycle.add(indiceDebut,sommet);



    }

    private int calculCoutTotal(ArrayList<Integer> listeCycle, boolean afficher)
    {

       int somme1 =0;
       int somme2 = 0;
       for(int i = 0 ; i < listeCycle.size(); i++)
       {
           if( i ==  listeCycle.size()-1)
              somme1 += coutCycle[listeCycle.get(i)-1][0] ;
           else
              somme1 += coutCycle[listeCycle.get(i)-1][listeCycle.get(i+1)-1] ;
       }
       for(int i = 0 ; i < sommetsRestants.size(); i++)
       {
           int plusProche = plusProcheSommetCycle(sommetsRestants.get(i));
           somme2 += coutAffectation[sommetsRestants.get(i)-1][plusProche-1] ;
       }
       int cout = somme1+somme2;
       
       if(afficher)
       {
            System.out.println("\nCycle de départ : ");

            for(int i = 0 ; i < listeCycle.size() ; i ++)
                 System.out.print(listeCycle.get(i) + " -> ");
            System.out.println("\nCout total initial : " + (somme1+somme2));
       }
       
       return cout;

    }
    /*public boolean checkAjoutCycle()
    {
        //test
        if(sommetsCycle.size() > 3)
        {
                return false;
        }

        return true;
    }*/


    private void creerCycleMin() {
        
        double coutCycleMin = 99999999;
        int sommet =0;

        ajouterSommet(1,-1);
        for(int i=0; i<2; i++){
            for(int j=0 ; j<sommetsRestants.size() ; j++){
                int som1 = sommetsCycle.get(i);
                int  som2 = sommetsRestants.get(j);
                if((coutCycle[som1-1][som2-1] < coutCycleMin) && som1 != som2){
                    coutCycleMin = coutCycle[som1-1][som2-1];
                    sommet = som2;
                
                }             
            }
            //nouveau parcours de coutCycle
            coutCycleMin = 99999999;
            ajouterSommet(sommet,-1);
        }
    }

    public void printCycle()
    {
        System.out.println( "Cycle final : ");
        for(int i = 0 ; i < sommetsCycle.size() ; i ++)
        {
            System.out.print(sommetsCycle.get(i) );

            if(i != sommetsCycle.size()-1 )
                  System.out.print( " -> ");
            else
                System.out.println( "");
        }
          

        System.out.println("Cout total final  : " + coutTotal + " (" + timeHeuristique +"ms)");
    }

    public void metaHeuristique() {
        
        //solution initiale
       ArrayList<Integer> bestSol=sommetsCycle;
       ArrayList<Arete> listeAretes = new ArrayList<Arete>();
       int it = 0;
       Arete a= null;

       /* crée notre liste d'aretes */
       for(int i = 0 ; i < sommetsCycle.size(); i++)
        {
            if(i == sommetsCycle.size()-1)
            {
                a = new Arete(sommetsCycle.get(i), sommetsCycle.get(0));
                a.setCout(coutCycle[sommetsCycle.get(i)-1][sommetsCycle.get(0)-1]);

            }
            else{
                a = new Arete(sommetsCycle.get(i), sommetsCycle.get(i+1));
                a.setCout(coutCycle[sommetsCycle.get(i)-1][sommetsCycle.get(i+1)-1]);
            }
            listeAretes.add(a);
        }

       List<Arete> tabouIn = new ArrayList<Arete>();
       List<Arete> tabouOut = new ArrayList<Arete>();
       List<Integer> tabouSuppr = new ArrayList<Integer>();
       List<Integer> tabouAjout = new ArrayList<Integer>();


       do{
           // génere un nombre aléatoire à chaque tour de boucle
           // ce nb détermine la méthode utilisée
           Random random = new Random();
           int r = random.nextInt(20);

           /* décrémente les compteurs de tour pour chaque arête dans le tabou */
           for(int k = 0 ; k < tabouIn.size() ; k++)
           {
               tabouIn.get(k).setTempsRestant(tabouIn.get(k).getTempsRestant()-1);
               if(tabouIn.get(k).getTempsRestant() == 0)
                    tabouIn.remove(k);
           }
           for(int k = 0 ; k < tabouOut.size() ; k++)
           {
               tabouOut.get(k).setTempsRestant(tabouOut.get(k).getTempsRestant()-1);
               if(tabouOut.get(k).getTempsRestant() == 0)
                    tabouOut.remove(k);
           }

           if(r<=20){
               //mouvement des arcs : faible pourcentage car tres couteux
               // Par contre, calcul du cout tres rapide 

               double meilleurCout = Integer.MAX_VALUE;
               ArrayList<Integer> meilleurCycle = null;
               Arete meilleureArete1 = null;
               Arete meilleureArete2 = null;

               // choisi la meilleure combinaison d'arêtes
               for(int i=0; i<listeAretes.size(); i++){
                   if(i == listeAretes.size() -1 )
                       i = -1;
                   for(int j=i+1; j<listeAretes.size(); j++){
                       if(i == -1)
                           i =listeAretes.size()-1;
                       ArrayList<Integer> tmp = (ArrayList)sommetsCycle.clone();
                       boolean isInTabou = false;
                       for(int k = 0 ; k < tabouIn.size() ; k++)
                       {
                           if(tabouIn.get(k).getSommet1() == listeAretes.get(i).getSommet1() && tabouIn.get(k).getSommet2() == listeAretes.get(i).getSommet2())
                                isInTabou = true;
                       }
                       for(int k = 0 ; k < tabouOut.size() ; k++)
                       {
                           if(tabouOut.get(k).getSommet1() == listeAretes.get(i).getSommet1() && tabouOut.get(k).getSommet2() == listeAretes.get(i).getSommet2())
                                isInTabou = true;
                       }
                       if(!isInTabou)
                       {

                           double coutActuel = coutMouvement(listeAretes.get(i), listeAretes.get(j), tmp);
                           if(coutActuel < meilleurCout){
                                meilleurCout = coutActuel;
                                meilleureArete1 = listeAretes.get(i);
                                meilleureArete2 = listeAretes.get(j);
                                meilleurCycle = (ArrayList)tmp.clone();
                           }
                       }
                   }
               }
               if(meilleureArete1 != null && meilleureArete2 != null)
               {
                    Arete areteIn1 = new Arete(meilleureArete1.getSommet1(), meilleureArete1.getSommet2());
                    areteIn1.setCout(coutCycle[meilleureArete1.getSommet1()-1][ meilleureArete1.getSommet2()-1]);
                    Arete areteIn2 = new Arete(meilleureArete2.getSommet1(), meilleureArete2.getSommet2());
                    areteIn2.setCout(coutCycle[meilleureArete2.getSommet1()-1][ meilleureArete2.getSommet2()-1]);
                    listeAretes = ajouterAretes(areteIn1, areteIn2, listeAretes);
                    tabouIn.add(areteIn1);
                    tabouIn.add(areteIn2);

                    Arete areteOut1 = new Arete(meilleureArete1.getSommet1(), meilleureArete2.getSommet1());
                    areteOut1.setCout(coutCycle[meilleureArete1.getSommet1()-1][ meilleureArete2.getSommet1()-1]);
                    Arete areteOut2 = new Arete(meilleureArete1.getSommet2(), meilleureArete2.getSommet2());
                    areteOut2.setCout(coutCycle[meilleureArete1.getSommet2()-1][ meilleureArete2.getSommet2()-1]);
                    listeAretes = supprimerAretes(areteOut1,areteOut2, listeAretes);
                    tabouOut.add(areteOut1);
                    tabouOut.add(areteOut2);

                   coutTotal = meilleurCout;
                   sommetsCycle.clear();
                   sommetsCycle = (ArrayList<Integer>)meilleurCycle.clone();
                }

           }else if(r>=20 && r<60){
               //suppression sommet

               double meilleurCout = Integer.MAX_VALUE;
               int indiceSommetAsupprimer = -1;
              int  sommetAsupprimer = -1;

                for(int i=0; i<sommetsCycle.size(); i++){
                   ArrayList<Integer> tmp = (ArrayList)sommetsCycle.clone();
                   tmp.remove(i);
                   double coutActuel = calculCoutTotal(tmp, false);
                   if(coutActuel < meilleurCout){
                        meilleurCout = coutActuel;
                        indiceSommetAsupprimer = i;
                        sommetAsupprimer = sommetsCycle.get(i);
                   }
               }

               coutTotal = meilleurCout;
               //supprime les 2 arêtes entre le précédent et le sommet suppr, puis entre le sommet suppr et le suivant
               for(int i = 0; i< listeAretes.size() ; i++)
               {
                   if(listeAretes.get(i).getSommet1() == sommetsCycle.get(indiceSommetAsupprimer) || listeAretes.get(i).getSommet2() == sommetsCycle.get(indiceSommetAsupprimer))
                        listeAretes.remove(i);
               }
               
               // ajoute la nouvelle arete entre le précédent et le suivant de celui supprimé
               if(indiceSommetAsupprimer == sommetsCycle.size()-1)
               {
                    a = new Arete(sommetsCycle.get(indiceSommetAsupprimer-1), sommetsCycle.get(0));
                    a.setCout(coutCycle[sommetsCycle.get(indiceSommetAsupprimer-1)-1][sommetsCycle.get(0)-1]);
               } else if(indiceSommetAsupprimer == 0){
                    a = new Arete(sommetsCycle.get(sommetsCycle.size()-1), sommetsCycle.get(1));
                    a.setCout(coutCycle[sommetsCycle.get(sommetsCycle.size()-1)-1][sommetsCycle.get(1)-1]);
               }else{
                    a = new Arete(sommetsCycle.get(indiceSommetAsupprimer-1), sommetsCycle.get(indiceSommetAsupprimer+1));
                    a.setCout(coutCycle[sommetsCycle.get(indiceSommetAsupprimer-1)-1][sommetsCycle.get(indiceSommetAsupprimer+1)-1]);
               }
               listeAretes.add(a);

               sommetsCycle.remove(indiceSommetAsupprimer);
               sommetsRestants.add(sommetAsupprimer);

               coutTotal = calculCoutTotal(sommetsCycle, false);


           }else if(r>=60 && r<100){
               if(!sommetsRestants.isEmpty())
               {
                    //insertion sommet
                    Random random2 = new Random();
                    int position = 0;
                    int indiceSommetAjoute = 0;
                    int sommetAjoute = 0;

                    //choix aléatoire de suppression
                    indiceSommetAjoute = random.nextInt(sommetsRestants.size());
                    if(!tabouAjout.contains(sommetsRestants.get(indiceSommetAjoute)))
                    {
                        sommetAjoute = sommetsRestants.get(indiceSommetAjoute);
                        sommetsRestants.remove(indiceSommetAjoute);

                        position = random2.nextInt(sommetsCycle.size());
                        tabouAjout.add(sommetAjoute);
                        for(int i =0 ; i < listeAretes.size() ; i++)
                        {
                            if(listeAretes.get(i).getSommet2() == sommetsCycle.get(position))
                                listeAretes.remove(i);
                        }
                        Arete newArete = new Arete(sommetAjoute, sommetsCycle.get(position));
                        newArete.setCout(coutCycle[sommetAjoute-1][sommetsCycle.get(position)-1]);
                        listeAretes.add(newArete);
                        ajouterSommet(sommetAjoute, position-1);

                    }
               }
            }

           it++;
       }while(it<iterationMax);
    }

    /*
     *return le cout du mouvement
     */
    public double coutMouvement(Arete a1, Arete a2, ArrayList<Integer> tmp){

        int indice1=-1;
        int indice2=-1;
        int indice3=-1;
        int indice4=-1;

        /*inversion de deux sommets d'arete differente relies par un arc*/
        // récupère les indices dans le cycle, des 2 aretes à échanger ( 4 sommets)
        for(int i = 0; i < tmp.size() ; i ++){
            if(tmp.get(i)==a1.getSommet1())
                indice1 = i;
            if(tmp.get(i)==a1.getSommet2())
                indice2 = i;
            if(tmp.get(i)==a2.getSommet1())
                indice3 = i;
            if(tmp.get(i)==a2.getSommet2())
                indice4 = i;
        }

        List<Integer> listIndices = Arrays.asList(indice1,indice2,indice3,indice4);
        //ordonne la liste des indices par ordre
        // les 2 sommets à inverser sont donc en position 1 et 2 de la liste d'indices ordonnée
        Collections.sort(listIndices);
        double cout = coutTotal;
        if(listIndices.get(1) != listIndices.get(2)) // si ce n'est pas le même sommet 2 fois ( ex : 1-32 - 32 - 27 )
        {
            /* Calcul du nouveau cout - mouvement ab-cd donne ac-bd : ab et cd enlevés, ac et bd ajoutés*/
            double coutEnleve = coutCycle[tmp.get(listIndices.get(0))-1][tmp.get(listIndices.get(1))-1] + coutCycle[tmp.get(listIndices.get(2))-1][tmp.get(listIndices.get(3))-1];
            double coutAjoute = coutCycle[tmp.get(listIndices.get(0))-1][tmp.get(listIndices.get(3))-1] + coutCycle[tmp.get(listIndices.get(1))-1][tmp.get(listIndices.get(2))-1];

            cout = cout - coutEnleve + coutAjoute;

            tmp = inverserSommets(listIndices.get(1), listIndices.get(2), tmp);
        }
        return cout;
    }

    public ArrayList<Integer>  inverserSommets(int indice1, int indice2, ArrayList<Integer> liste){
        int tmp = liste.get(indice1);
        liste.set(indice1, liste.get(indice2));
        liste.set(indice2, tmp);

        return liste;
    }

    private ArrayList<Arete> ajouterAretes(Arete areteIn1, Arete areteIn2, ArrayList<Arete> listeAretes) {
        listeAretes.add(areteIn1);
        listeAretes.add(areteIn2);
        return listeAretes;
    }

    private ArrayList<Arete> supprimerAretes(Arete areteOut1, Arete areteOut2, ArrayList<Arete> listeAretes) {
        for(int i = 0 ; i < listeAretes.size() ; i++)
        {
            if(listeAretes.get(i).getSommet1() == areteOut1.getSommet1() && listeAretes.get(i).getSommet2() == areteOut1.getSommet2())
                listeAretes.remove(i);

            if(listeAretes.get(i).getSommet1() == areteOut2.getSommet1() && listeAretes.get(i).getSommet2() == areteOut2.getSommet2())
                listeAretes.remove(i);
        }
        return listeAretes;
    }


}
